#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Point {
  int x;
  int y;
  int dist;
  Point(int _x, int _y, int _dist) : x(_x), y(_y), dist(_dist) {}
};

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
  int m = grid.size();
  int n = grid[0].size();

  if (grid[0][0] == 1 || grid[m-1][n-1] == 1) {
    return -1; 
  }

  vector<vector<int>> visited(m, vector<int>(n, 0));

  queue<Point> q;
  q.push(Point(0, 0, 1));

  while (!q.empty()) {
    Point p = q.front();
    q.pop();

    int x = p.x;
    int y = p.y;
    int dist = p.dist;

    if (x == m-1 && y == n-1) { 
      return dist;
    }

    if (visited[x][y]) {
      continue;
    }
    visited[x][y] = 1;

    for (int dx = -1; dx <= 1; dx++) {
      for (int dy = -1; dy <= 1; dy++) {
        int nx = x + dx;
        int ny = y + dy;

        if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] != 1) {
          q.push(Point(nx, ny, dist+1));
        }
      }
    }
  }

  return -1; 
}

int main() {
  vector<vector<int>> grid = {
    {0, 1, 0, 0},
    {0, 0, 0, 1},
    {0, 1, 0, 0},
    {0, 0, 1, 0}
  };

  int shortestPath = shortestPathBinaryMatrix(grid);

  cout << "最短路径长度为：" << shortestPath << endl;

  return 0;
}